Informatics Publishing Limited

Neelam Tyagi ¹, R. P. Tripathi ¹, A. B. Chandramouli ²

Affiliations
1 Department of Mathematics, Graphic Era University, Dehradu – 248002, Uttarakhand, IN
2 Department of Mathematics, Meerut College, Meerut – 250003, Uttar Pradesh, IN

Abstract

Objectives: In this paper, we consider the Flexible Flowshop Scheduling (FFS) problem with parallel machines. The main objective of this paper is to obtain a good schedule of jobs to minimize the makespan of FFS problem. Methods/Statistical analysis: In this study, two heuristic algorithms have been developed of FFS to reduce the makespan. First, we constructed the new heuristic algorithm based on Minimum Processing Time Selective Approach (MPTSA) and Longest Processing Times (LPT) approach to find the optimal or near optimal sequence for minimization of makespan of FFS problem with parallel machines. Next, we developed the heuristic algorithm using PALMER approach. In the PALMER approach we sequence the jobs based on Longest Slope Value (LSV) and obtained the value of objective function. Findings: We compared both the heuristic algorithms with the help of numerical illustrations. We solved the same numerical by both the heuristic algorithm and result show that our constructed heuristic algorithm has resulted in a better industrial production makespan. The percentage improvement of our constructive heuristic algorithm is also calculated. Gantt chart is also generated to verify the effectiveness of constructed heuristic algorithm. Application/Improvements: Our constructed heuristic algorithm is more effective to reduced the makespan of FFS problems as compare to classic heuristic algorithm as Palmer approach and provide an important tool for decision makers in production management.

Keywords

Flexible Flowshop Scheduling, Gantt Chart, LPT Approach, Makespan, MPTSA Approach, Parallel Machines, Percentage Improvement.

Full Text

   

Neelam Tyagi ¹, R. P. Tripathi ¹, A. B. Chandramouli ²

Affiliations
1 Department of Mathematics, Graphic Era University, Dehradun - 248002, Uttarakhand, IN
2 Department of Mathematics, Meerut College, Meerut - 250001, Uttar Pradesh, IN

Abstract

Objectives: In this paper, Five Dispatching Rules and a Branch & Bound algorithm is introduced for Single Machine Total Tardiness Scheduling Problem (SMTTSP) to minimize the total (average) tardiness and number of tardy jobs. Methods/Statistical Analysis: We proposed five dispatching (priority) rules as Shortest Processing Time, Earliest Due Dates, Longest Processing Time, Minimum Slack Time and First Come First Serve for SMTTSP and compared the performance of all the proposed priority rules. Furthermore, a numerical illustrations is also provided to select the best dispatched rule of SMTTSP. Next, we developed a Branch & Bound Algorithm for SMTTSP using best selected dispatching rule. We also developed Branch Tree to understand the Lower bound process of the B& B Algorithm. Findings: The main aim to proposed these dispatching rules and a Branch and Bound Algorithm is to obtain the optimal sequence to optimize the total (average) tardiness and number of total tardy jobs. The comparative analysis of the dispatching rules shows that EDD rule is better than other dispatching rules for minimization of total tardy jobs and tardiness of the jobs while SPT rule is better for minimization of make span. But Dispatching rules do not have the guarantee to give an optimal solution. So in this study, an exact algorithm (Branch & Bound) was developed with EDD rule for finding the optimal solution for SMTTSP. The comparative study between dispatching rules and an exact (B&B) algorithm is being justified by numerical illustrations and we found that the EDD rule and B&B Algorithm give the same results. Hence it was concluded that EDD rule works as an Exact algorithm and gives the optimal solution for SMTTSP. Application/Improvements: The computational results of the proposed (B&B) algorithm and Dispatching rules show that our methodology is more useful than other optimal approach for SMTTSP and it provides an important tool for decision makers.

Keywords

Average Completion Time, (Average) Tardiness of Jobs, Branch and Bound Algorithm, Branch Tree, No of Tardy Jobs, Single Machine Scheduling.

Full Text

   

Neelam Tyagi ¹, R. P. Tripathi ¹, A. B. Chandramouli ²

Affiliations
1 Department of Mathematics, Graphic Era University, Dehradun – 248002, Uttarakhand, IN
2 Department of Mathematics, Meerut College, Meerut – 250001, Uttar Pradesh, IN

Abstract

Objectives: We proposed two heuristic algorithms for Total Weighted Due Date Tardiness Scheduling (TWDDTS). The main aim of this paper is to optimize the weighted tardiness based criteria. Methods/Statistical Analysis: The first one heuristic algorithm for 'TWDDTS' is based on dispatching rule (EDD-Earliest Due Date) and the second one heuristic algorithm for Modified Total Weighted Due Date Tardiness Scheduling (MTWDDTS) is based on modified weighed due dates. We equated the effectiveness of both the proposed heuristic algorithms with the help of numerical illustrations. Findings: The main aim to propose these heuristic algorithms is to obtain the optimal solution of the problem related to weighted tardiness scheduling based criteria, when processing times of the jobs are also associated with probabilities. These heuristic algorithms are justified by numerical illustrations and comparative study of both the heuristic algorithms (with the help of numerical example) show that an improved heuristic algorithm for MTWDDTS is outperform and give better results than a TWDDTS heuristic algorithm. We also found that when we measure the mean completion time of jobs by both the heuristic algorithms then we observed that the MTWDDTS heuristic algorithm gives the best result as compared to a TWDDTS heuristic algorithm. So we find that MTWDDTS gives the best result for minimization the weighted tardiness based criteria as well as makespan. Application/Improvements: The proposed MTWDDTS algorithm is more useful than the EDD dispatching rule for weighted tardiness based scheduling problems. It is easy to understand and provide an important tool for decision makers.

Keywords

EDD Dispatching Rule, Modified Weighted Due Dates (MWDD), Single Machine Scheduling, Stochastic Processing Time, Weighted Tardiness.

Full Text

   

Neelam Tyagi ¹, R. P. Tripathi ¹, A. B. Chandramouli ²

Affiliations
1 Department of mathematics, Graphic Era University, Dehradun - 248002, Uttarakhand, IN
2 Department of mathematics, Meerut College, Meerut - 250003, Uttar Pradesh, IN

Abstract

Objectives: To find the optimum solution for minimization of bicriterion (makespan, weighted mean flowtime) objective function of three machines flowshop scheduling problem with transportation times and weight of the jobs. Methods/Statistical Analysis: In this paper, we used two types of methodologies first one is based on a Branch and Bound (B&B) technique of exact algorithms and second one is based on Palmer approach of heuristic algorithms. First of all, we originated a new algorithm using B&B technique later on; we developed a new heuristic algorithm using Palmer approach for obtaining the optimal or near optimal sequence to minimize the bicriterion objective function of three machines scheduling problem in flowshop environments with transportation times and weights of the jobs. Comparative study between both the proposed algorithms is also considered to select the best methodology of our bicriterion objective function with the help of numerical illustration. Directed graphs, Gantt chart and Branch Tree are also generated to understand the process of lower bound and effectiveness of proposed algorithms. Findings: We solved the same numerical by constructed Branch & Bound (B&B) algorithm and Palmer based heuristic algorithm. Hence, comparatative result show that our originated B&B algorithm gives the optimal solution or better result as compare to Palmer based heuristic algorithm for minimization of bicriterion (makespan and weighted mean flowtime) objective function. We also calculated the percentage improvement of our constructive B&B algorithm over palmer based new heuristic algorithm and it is examined that constructive B&B algorithm gives the 8.33% improvement in make span and 6.52% improvement in weighted mean flowtime. The directed graph of each computational level is also originated to understand the computational process of the lower bounds easily. The Gantt chart between both the proposed algorithms is also generated to verify the effectiveness of new originated B&B algorithm. Directed graph is also generated of the optimal sequence. Finally, Branch Tree is generated to empathize the process of Lower Bound. Application/Improvements: Our constructed B&B algorithm provide an important tool for decision maker to minimize the makespan and weighted mean flowtime together as bicriterion objective function of three machine flowshop scheduling problems.

Keywords

Algorithm, Branch Tree, Branch & Bound, Directed Graph, Gantt Chart, Makespan, Percentage Improvements, Three Machines Scheduling, Transportation Time, Weighted Mean Flowtime.

Full Text